/*
 * @lc app=leetcode.cn id=86 lang=cpp
 *
 * [86] 分隔链表
 */

// @lc code=start
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    // ListNode* partition(ListNode* head, int x) {
    //     ListNode* minhead = new ListNode(0);
    //     ListNode* maxhead = new ListNode(0);
    //     ListNode* p_min = minhead;
    //     ListNode* p_max = maxhead;
    //     ListNode* p = head;

    //     while(p!=NULL)
    //     {
    //         if(p->val >= x)
    //         {
    //             p_max->next = p;
    //             p_max = p_max->next;
    //             p = p->next; 
    //         }
    //         else
    //         {
    //             p_min->next = p;
    //             p_min = p_min->next;
    //             p = p->next;
    //         }
    //     }
    //     p_min->next = maxhead->next;
    //     p_max->next = NULL;
    //     // ListNode* res = minhead->next;
    //     // delete minhead;
    //     // delete maxhead;
    //     return minhead->next;
    // }

        ListNode* partition(ListNode* head, int x) {
        ListNode* minhead = new ListNode(0);
        ListNode* maxhead = new ListNode(0);
        ListNode* p_min = minhead;
        ListNode* p_max = maxhead;

        while(head!=NULL)
        {
            if(head->val >= x)
            {
                p_max->next = head;
                p_max = p_max->next;
                head = head->next; 
            }
            else
            {
                p_min->next = head;
                p_min = p_min->next;
                head= head->next;
            }
        }
        p_min->next = maxhead->next;
        p_max->next = NULL;
        // ListNode* res = minhead->next;
        // delete minhead;
        // delete maxhead;
        return minhead->next;
    }
};
// @lc code=end

